On considère une source \(X\) sur un alphabet \(\mathcal X=\{x_1,\dots,x_M\}\) et on note \(p_i=p_X(x_i)\). On suppose que \(p_1\gt p_2\geqslant\dots\geqslant p_M\).
Montrer que pour tout code de Huffman binaire, si \(p_1\lt \frac13\), alors le symbole \(x_1\) doit être codé sur au moins 2 bits.

On suppose par l'absurde que c'est faux et on dessine un tel arbre.

Déduire de l'information sur \(p_1\) et de la structure de l'arbre des informations sur \(p_2\) et \(p_3\).

Cela nous donne un échange possible qui raccourci la longueur moyenne des mots, ce qui rend la construction absurde par optimalité du code de Huffman.

On considère une source \(X\) sur un alphabet \(\mathcal X=\{x_1,\dots,x_M\}\) et on note \(p_i=p_X(x_i)\). On suppose que \(p_1\gt p_2\geqslant\dots\geqslant p_M\).
Montrer que pour tout code de Huffman binaire, si \(p_1\gt \frac25\), alors le symbole \(x_1\) doit être codé sur un bit.

On suppose par l'absurde que c'est faux et on construit un tel arbre.

On en déduit des infos sur l'autre couple d'ensemble de symboles, quitte à permuter.

On peut alors faire des modifications sur l'arbre et avoir un meilleur code, ce qui est absurde par optimalité du code de Huffman.